package 构造二叉树;

import java.util.Arrays;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 从中序与后序遍历序列构造二叉树
 * @date 2022/11/6 13:05
 */
public class Demo106 {
    //inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
    //输出：[3,9,20,null,null,15,7]
    public static void main(String[] args) {
      int[] inorder = {9,3,15,20,7};
      int[] postorder = {9,15,7,20,3};
        TreeNode treeNode = buildTree(inorder, postorder);
        System.out.println(treeNode);

    }
    //递归参数和返回值
    public  static TreeNode buildTree(int[] inorder, int[] postorder) {
        //2.递归返回值
        //后续的长度是0，返回null
        if(postorder.length==0){
            return null;
        }
        //开始递归
        //通过后续确定中节点
        TreeNode root=new TreeNode(postorder[postorder.length-1]);
        if(postorder.length==1){
            return root;
        }
        //通过后续找到的根节点，去找中序里面根的位置，分割数组
        int index=0;
        for (int i = 0; i < inorder.length; i++) {
            if(inorder[i]==root.val){
                break;
            }
            index++;
        }
        //index即为中序中根节点的位置
        //分割中序数组
        int[] inorderInorder = Arrays.copyOfRange(inorder, 0, index);
        int[] inorderPostorder = Arrays.copyOfRange(inorder, index+1, inorder.length);
        int[] postorderInorder = Arrays.copyOfRange(postorder, 0, inorderInorder.length);
        int[] postorderPostorder = Arrays.copyOfRange(postorder, inorderInorder.length, postorder.length-1);
        root.left=buildTree(inorderInorder,postorderInorder);
        root.right=buildTree(inorderPostorder,postorderPostorder);
        return root;

    }



    //Definition for a binary tree node.
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}
